package main

import (
	"fmt"
	"math"
)

//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与
// target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
//示例:
//例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
//
//与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

func quicksort(arr []int, left, right int){
	if left >= right{
		return
	}

	i, j := left, right
	key := arr[i]
	for i < j{
		for ;i < j; j--{
			if arr[j] < key{
				break
			}
		}
		arr[i] = arr[j]

		for ; i < j; i++{
			if arr[i] > key{
				break
			}
		}
		arr[j] = arr[i]
	}
	arr[i] = key
	quicksort(arr, left, i)
	quicksort(arr, i+1, right)
}

func threeNumberSum(nums []int, target int) []int{
	quicksort(nums, 0, len(nums)-1)
	iSum := 0xFFFFFFFF
	result := []int{}
	for k, v := range nums{
		i, j := k+1, len(nums)-1
		for i <j{
			if i == k{
				i++
				continue
			}
			if j == k{
				j--
				continue
			}
			sum := v + nums[i] + nums[j] - target
			if math.Abs(float64(iSum)) > math.Abs(float64(sum)){
				iSum = sum
				result = []int{v, nums[i], nums[j]}
			}

			if sum < 0{
				i++
			}else if sum > 0{
				j--
			}else{
				result = []int{v, nums[i], nums[j]}
				return result
			}
		}
	}
	return result
}

func main(){
	fmt.Println(threeNumberSum([]int{-1, 2, 1, -4}, 1))
}